package main

import "fmt"

//给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。 
//
// 请你找出并返回只出现一次的那个数。 
//
// 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,1,2,3,3,4,4,8,8]
//输出: 2
// 
//
// 示例 2: 
//
// 
//输入: nums =  [3,3,7,7,10,11,11]
//输出: 10
// 
//
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 10⁵ 
// 0 <= nums[i] <= 10⁵ 
// 
// Related Topics 数组 二分查找 👍 374 👎 0
func main() {
	fmt.Println(singleNonDuplicate([]int{1,1,2,3,3,4,4,8,8}))
}

//leetcode submit region begin(Prohibit modification and deletion)
func singleNonDuplicate(nums []int) int {
	// 可以按长度来算，有单一元素的那部分的长度一定是奇数
	
	// 终止条件
	if len(nums) == 1 {
		return nums[0]
	}
	
	// 开始二分
	// 如果最中间的数与后一个相等，则从该位置前边拆分
	// 如果最中间的数和前一个相等，则从该位置后边拆分
	if nums[(len(nums) - 1) / 2] == nums[(len(nums) - 1) / 2 + 1] {
		if isOdd(len(nums[:(len(nums) - 1) / 2])) {
			return singleNonDuplicate(nums[:(len(nums) - 1) / 2])
		} else {
			return singleNonDuplicate(nums[(len(nums) - 1) / 2:])
		}
	} else if nums[(len(nums) - 1) / 2] == nums[(len(nums) - 1) / 2 - 1] {
		if isOdd(len(nums[:(len(nums) - 1) / 2 + 1])) {
			return singleNonDuplicate(nums[:(len(nums) - 1) / 2 + 1])
		} else {
			return singleNonDuplicate(nums[(len(nums) - 1) / 2 + 1:])
		}
	} else {
		return nums[(len(nums) - 1) / 2]
	}
}

func isOdd(l int) bool {
	return (l / 2) * 2 != l 
}
//leetcode submit region end(Prohibit modification and deletion)


